package com.demo.java.OD451_500.OD475;

import java.util.*;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 【快递员的烦恼(C&D卷)】问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/146354552
 */
public class OdMain {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 读取客户数 n 和客户之间的路径数 m
        int n = scanner.nextInt();
        int m = scanner.nextInt();

        // 记录客户之间的距离
        Integer[][] distances = new Integer[n + 1][n + 1];
        Map<Integer, Integer> mapping = new HashMap<>();

        // 读取投递站到客户的距离
        for (int i = 1; i <= n; i++) {
            int uid = scanner.nextInt();  // 客户ID
            int d = scanner.nextInt();    // 投递站到该客户的距离
            mapping.put(uid, i);
            distances[0][i] = distances[i][0] = d;
        }

        // 读取客户之间的路径信息
        for (int i = 0; i < m; i++) {
            int x = scanner.nextInt();
            int y = scanner.nextInt();
            int d = scanner.nextInt();
            x = mapping.get(x);
            y = mapping.get(y);
            distances[x][y] = distances[y][x] = d; // 存入无向图
        }

        // DP 数组：dp[state][i] 记录访问状态 state 下，停留在 i 号客户的最短路径
        Integer[][] dp = new Integer[1 << n][n + 1];

        // BFS 队列存储状态 (当前状态, 当前客户编号, 当前总距离)
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{0, 0, 0}); // 初始状态，位于投递站
        dp[0][0] = 0;

        // BFS 遍历所有可能的路径
        while (!queue.isEmpty()) {
            int[] state = queue.poll();
            int nowState = state[0]; // 当前已访问客户集合
            int now = state[1];      // 当前所在客户编号
            int nowD = state[2];     // 当前路径长度

            for (int nxt = 0; nxt <= n; nxt++) {
                if (nxt != now && distances[now][nxt] != null) { // 存在路径
                    int nextState;
                    if (nxt == 0) {
                        nextState = nowState; // 回到投递站，不改变状态
                    } else {
                        nextState = nowState | (1 << (nxt - 1)); // 访问新客户
                    }

                    // 如果未访问或者找到更短路径，更新 dp
                    if (dp[nextState][nxt] == null || dp[nextState][nxt] > dp[nowState][now] + distances[now][nxt]) {
                        dp[nextState][nxt] = dp[nowState][now] + distances[now][nxt];
                        queue.add(new int[]{nextState, nxt, dp[nextState][nxt]});
                    }
                }
            }
        }

        // 输出访问所有客户并返回投递站的最短路径
        System.out.println(dp[(1 << n) - 1][0]);
    }
}